/*
 * Heap.c
 *
 *  Created on: 2011-7-7
 *      Author: Donghan
 */
/*
 * Garbage-collecting memory allocator
 */
#include "../Dalvik.h"
#include "HeapTable.h"
#include "Heap.h"
#include "HeapInternal.h"
#include "HeapSource.h"

#include "../../includes/utils/threads.h"      // need Android thread
#define kInvalidPriority        10000
#include <errno.h>

static const char* GcReasonStr[] = {
		[GC_FOR_MALLOC] = "GC_FOR_MALLOC",
		[GC_CONCURRENT] = "GC_CONCURRENT",
		[GC_EXPLICIT] = "GC_EXPLICIT",
		[GC_EXTERNAL_ALLOC] = "GC_EXTERNAL_ALLOC",
		[GC_HPROF_DUMP_HEAP] = "GC_HPROF_DUMP_HEAP"
};

/*
 * Initialize the GC heap.
 *
 * Returns true if successful, false otherwise.
 */bool dvmHeapStartup() {
	GcHeap *gcHeap;

#if defined(WITH_ALLOC_LIMITS)
	gDvm.checkAllocLimits = false;
	gDvm.allocationLimit = -1;
#endif

	gcHeap = dvmHeapSourceStartup(gDvm.heapSizeStart, gDvm.heapSizeMax);
	if (gcHeap == NULL) {
		return false;
	}

	gcHeap->heapWorkerCurrentObject = NULL;
	gcHeap->heapWorkerCurrentMethod = NULL;
	gcHeap->heapWorkerInterpStartTime = 0LL;
	gcHeap->ddmHpifWhen = 0;
	gcHeap->ddmHpsgWhen = 0;
	gcHeap->ddmHpsgWhat = 0;
	gcHeap->ddmNhsgWhen = 0;
	gcHeap->ddmNhsgWhat = 0;
#if WITH_HPROF
	gcHeap->hprofDumpOnGc = false;
	gcHeap->hprofContext = NULL;
#endif
	//对全局变量的gcHeap进行赋值
	gDvm.gcHeap = gcHeap;

	/* Set up the lists and lock we'll use for finalizable
	 * and reference objects.
	 */
	dvmInitMutex(&gDvm.heapWorkerListLock);
	/*存储一些当被垃圾回收时需要执行finalize方法的参考表*/
	gcHeap->finalizableRefs = NULL;
	/*存储一些需要执行finalize方法的对象的参考表，但是我没有看到在代码里何处往这个表中填入对象*/
	gcHeap->pendingFinalizationRefs = NULL;
	/*需要被执行clear或者enqueue方法的引用对象的列表*/
	gcHeap->referenceOperations = NULL;

	if (!dvmCardTableStartup()) {
		return false;
	}

	/* Initialize the HeapWorker locks and other state
	 * that the GC uses.
	 */
	dvmInitializeHeapWorkerState();

	return true;

}

bool dvmHeapStartupAfterZygote() {
	return dvmHeapSourceStartupAfterZygote();
}

void dvmHeapShutdown() {

	//TODO: make sure we're locked
	if (gDvm.gcHeap != NULL) {
		dvmCardTableShutdown();
		/* Tables are allocated on the native heap; they need to be
		 * cleaned up explicitly.  The process may stick around, so we
		 * don't want to leak any native memory.
		 */
		dvmHeapFreeLargeTable(gDvm.gcHeap->finalizableRefs);
		gDvm.gcHeap->finalizableRefs = NULL;

		dvmHeapFreeLargeTable(gDvm.gcHeap->pendingFinalizationRefs);
		gDvm.gcHeap->pendingFinalizationRefs = NULL;

		dvmHeapFreeLargeTable(gDvm.gcHeap->referenceOperations);
		gDvm.gcHeap->referenceOperations = NULL;

		/* Destroy the heap.  Any outstanding pointers will point to
		 * unmapped memory (unless/until someone else maps it).  This
		 * frees gDvm.gcHeap as a side-effect.
		 */
		dvmHeapSourceShutdown(&gDvm.gcHeap);
	}

}

/*
 * Shutdown any threads internal to the heap.
 */
void dvmHeapThreadShutdown(void) {
	dvmHeapSourceThreadShutdown();
}

/*
 * We've been asked to allocate something we can't, e.g. an array so
 * large that (length * elementWidth) is larger than 2^31.
 *
 * _The Java Programming Language_, 4th edition, says, "you can be sure
 * that all SoftReferences to softly reachable objects will be cleared
 * before an OutOfMemoryError is thrown."
 *
 * It's unclear whether that holds for all situations where an OOM can
 * be thrown, or just in the context of an allocation that fails due
 * to lack of heap space.  For simplicity we just throw the exception.
 *
 * (OOM due to actually running out of space is handled elsewhere.)
 */
void dvmThrowBadAllocException(const char* msg) {
	dvmThrowException("Ljava/lang/InternalError;", msg);
}

/*
 * Grab the lock, but put ourselves into THREAD_VMWAIT if it looks like
 * we're going to have to wait on the mutex.
 * 锁住heap，但要考虑heap锁的问题
 */
bool dvmLockHeap() {
	if (dvmTryLockMutex(&gDvm.gcHeapLock) != 0) {
		Thread *self;
		ThreadStatus oldStatus;

		self = dvmThreadSelf();
		oldStatus = dvmChangeStatus(self, THREAD_VMWAIT);
		dvmLockMutex(&gDvm.gcHeapLock);
		dvmChangeStatus(self, oldStatus);
	}

	return true;
}

//解除heap的锁
void dvmUnlockHeap() {
	dvmUnlockMutex(&gDvm.gcHeapLock);
}

/* Pop an object from the list of pending finalizations and
 * reference clears/enqueues, and return the object.
 * The caller must call dvmReleaseTrackedAlloc()
 * on the object when finished.
 *
 * 从finalizate队列中弹出一个对象
 * Typically only called by the heap worker thread.
 */
Object *dvmGetNextHeapWorkerObject(HeapWorkerOperation *op) {
	Object *obj;
	GcHeap *gcHeap = gDvm.gcHeap;

	assert(op != NULL);

	dvmLockMutex(&gDvm.heapWorkerListLock);

	obj = dvmHeapGetNextObjectFromLargeTable(&gcHeap->referenceOperations);
	if (obj != NULL) {
		*op = WORKER_ENQUEUE;
	} else {
		obj = dvmHeapGetNextObjectFromLargeTable(&gcHeap->pendingFinalizationRefs);
		if (obj != NULL) {
			*op = WORKER_FINALIZE;
		}
	}

	if (obj != NULL) {
		/* Don't let the GC collect the object until the
		 * worker thread is done with it.
		 */
		dvmAddTrackedAlloc(obj, NULL);
	}

	dvmUnlockMutex(&gDvm.heapWorkerListLock);

	return obj;
}

/* Do a full garbage collection, which may grow the
 * heap as a side-effect if the live set is large.
 * 做一次全收集垃圾
 */
static void gcForMalloc(bool collectSoftReferences) {

	if (gDvm.allocProf.enabled) {
		Thread* self = dvmThreadSelf();
		gDvm.allocProf.gcCount++;
		if (self != NULL) {
			self->allocProf.gcCount++;
		}
	}
	/* This may adjust the soft limit as a side-effect.
	 */
	dvmCollectGarbageInternal(collectSoftReferences, GC_FOR_MALLOC);

}

/* Try as hard as possible to allocate some memory.
 */
static void *tryMalloc(size_t size) {
	void *ptr;

	/* Don't try too hard if there's no way the allocation is
	 * going to succeed.  We have to collect SoftReferences before
	 * throwing an OOME, though.
	 */
	if (size >= gDvm.heapSizeMax) {
		ptr = NULL;
		goto collect_soft_refs;
	}

	//TODO: figure out better heuristics
	//    There will be a lot of churn if someone allocates a bunch of
	//    big objects in a row, and we hit the frag case each time.
	//    A full GC for each.
	//    Maybe we grow the heap in bigger leaps
	//    Maybe we skip the GC if the size is large and we did one recently
	//      (number of allocations ago) (watch for thread effects)
	//    DeflateTest allocs a bunch of ~128k buffers w/in 0-5 allocs of each other
	//      (or, at least, there are only 0-5 objects swept each time)

	ptr = dvmHeapSourceAlloc(size);
	if (ptr != NULL) {
		return ptr;
	}

	/*
	 * The allocation failed.  If the GC is running, block until it
	 * completes and retry.
	 */
	if (gDvm.gcHeap->gcRunning) {
		/*
		 * The GC is concurrently tracing the heap.  Release the heap
		 * lock, wait for the GC to complete, and retrying allocating.
		 */
		dvmWaitForConcurrentGcToComplete();
		ptr = dvmHeapSourceAlloc(size);
		if (ptr != NULL) {
			return ptr;
		}
	}
	/*
	 * Another failure.  Our thread was starved or there may be too
	 * many live objects.  Try a foreground GC.  This will have no
	 * effect if the concurrent GC is already running.
	 */
	gcForMalloc(false);
	ptr = dvmHeapSourceAlloc(size);
	if (ptr != NULL) {
		return ptr;
	}

	/* Even that didn't work;  this is an exceptional state.
	 * Try harder, growing the heap if necessary.
	 */
	ptr = dvmHeapSourceAllocAndGrow(size);
	if (ptr != NULL) {
		size_t newHeapSize;

		newHeapSize = dvmHeapSourceGetIdealFootprint();
		//TODO: may want to grow a little bit more so that the amount of free
		//      space is equal to the old free space + the utilization slop for
		//      the new allocation.
		return ptr;
	}

	/* Most allocations should have succeeded by now, so the heap
	 * is really full, really fragmented, or the requested size is
	 * really big.  Do another GC, collecting SoftReferences this
	 * time.  The VM spec requires that all SoftReferences have
	 * been collected and cleared before throwing an OOME.
	 */
	//TODO: wait for the finalizers from the previous GC to finish
	collect_soft_refs: gcForMalloc(true);
	ptr = dvmHeapSourceAllocAndGrow(size);
	if (ptr != NULL) {
		return ptr;
	}
	//TODO: maybe wait for finalizers and try one last time

	//TODO: tell the HeapSource to dump its state
	dvmDumpThread(dvmThreadSelf(), false);

	return NULL;
}

/* Throw an OutOfMemoryError if there's a thread to attach it to.
 * Avoid recursing.
 *
 * The caller must not be holding the heap lock, or else the allocations
 * in dvmThrowException() will deadlock.
 */
static void throwOOME() {

}

/*
 * Allocate storage on the GC heap.  We guarantee 8-byte alignment.
 *
 * The new storage is zeroed out.
 *
 * Note that, in rare cases, this could get called while a GC is in
 * progress.  If a non-VM thread tries to attach itself through JNI,
 * it will need to allocate some objects.  If this becomes annoying to
 * deal with, we can block it at the source, but holding the allocation
 * mutex should be enough.
 *
 * In rare circumstances (JNI AttachCurrentThread) we can be called
 * from a non-VM thread.
 *
 * Use ALLOC_DONT_TRACK when we either don't want to track an allocation
 * (because it's being done for the interpreter "new" operation and will
 * be part of the root set immediately) or we can't (because this allocation
 * is for a brand new thread).
 *
 * Returns NULL and throws an exception on failure.
 *
 * TODO: don't do a GC if the debugger thinks all threads are suspended
 */
void* dvmMalloc(size_t size, int flags) {

}

/*
 * Returns true iff <obj> points to a valid allocated object.
 */bool dvmIsValidObject(const Object* obj) {

}

size_t dvmObjectSizeInHeap(const Object *obj) {
	return dvmHeapSourceChunkSize(obj);
}

static void verifyRootsAndHeap(void) {
}

/*
 * Initiate garbage collection.
 *
 * NOTES:
 * - If we don't hold gDvm.threadListLock, it's possible for a thread to
 *   be added to the thread list while we work.  The thread should NOT
 *   start executing, so this is only interesting when we start chasing
 *   thread stacks.  (Before we do so, grab the lock.)
 *
 * We are not allowed to GC when the debugger has suspended the VM, which
 * is awkward because debugger requests can cause allocations.  The easiest
 * way to enforce this is to refuse to GC on an allocation made by the
 * JDWP thread -- we have to expand the heap or fail.
 *
 *  在进行debugger挂起vm的时候不允许进行GC
 */
void dvmCollectGarbageInternal(bool clearSoftRefs, GcReason reason) {

    GcHeap *gcHeap = gDvm.gcHeap;
    u4 rootSuspend, rootSuspendTime, rootStart, rootEnd;
    u4 dirtySuspend, dirtyStart, dirtyEnd;
    u4 totalTime;
    size_t numObjectsFreed, numBytesFreed;
    size_t currAllocated, currFootprint;
    size_t extAllocated, extLimit;
    size_t percentFree;
    GcMode gcMode;
    int oldThreadPriority = kInvalidPriority;

    /* The heap lock must be held.
     * 垃圾回收必须单线程
     */
    if (gcHeap->gcRunning) {
        return;
    }

    //回收的模式
    gcMode = (reason == GC_FOR_MALLOC) ? GC_PARTIAL : GC_FULL;
    gcHeap->gcRunning = true;

    rootSuspend = dvmGetRelativeTimeMsec();
    dvmSuspendAllThreads(SUSPEND_FOR_GC);
    rootStart = dvmGetRelativeTimeMsec();
    rootSuspendTime = rootStart - rootSuspend;

    /*
     * If we are not marking concurrently raise the priority of the
     * thread performing the garbage collection.
     */
    if (reason != GC_CONCURRENT) {
    	/* Get the priority (the "nice" value) of the current thread.  The
    	 * getpriority() call can legitimately return -1, so we have to
    	 * explicitly test errno.
    	 */
    	errno = 0;
    	int priorityResult = getpriority(PRIO_PROCESS, 0);
    	if (errno != 0)
    	{

    	}
    	else if (priorityResult > ANDROID_PRIORITY_NORMAL)
    	{
         /* Current value is numerically greater than "normal", which
          * in backward UNIX terms means lower priority.
          */

    	}
    }
}

void dvmWaitForConcurrentGcToComplete(void) {

}
